We consider a sliding window W over a stream of characters from some alphabet of constant\nsize. We want to look up a pattern in the current sliding window content and obtain all positions of\nthe matches. We present an indexed version of the sliding window, based on a suffix tree. The data\nstructure of size ... has optimal time queries ... and amortized constant time updates,\nwhere m is the length of the query string and occ is its number of occurrences.
Loading....